﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics.Contracts;

namespace HeapModel.ProgInfo
{
	//build up the recursive type info during load and access it though this
	sealed class RecursiveTypeInfo
	{
		private readonly List<TypeIdentifier> m_types;
		private readonly Dictionary<TypeIdentifier, HashSet<TypeIdentifier>> m_recwith;

		/// <summary>
		/// Load the types in and compute "recursive" type information.
		/// </summary>
		public RecursiveTypeInfo(IEnumerable<TypeIdentifier> loadedTypes)
		{
			Contract.Requires(loadedTypes != null);
			Contract.Requires(!loadedTypes.Contains(null));

			this.m_types = new List<TypeIdentifier>(loadedTypes);
			this.m_recwith = new Dictionary<TypeIdentifier, HashSet<TypeIdentifier>>();

			foreach(TypeIdentifier tt in this.m_types)
				this.m_recwith.Add(tt, new HashSet<TypeIdentifier>());

			HashSet<TypeIdentifier> rectypeset = new HashSet<TypeIdentifier>();
			Stack<TypeIdentifier> psf = new Stack<TypeIdentifier>();
			HashSet<TypeIdentifier> alreadytried = new HashSet<TypeIdentifier>();
			HashSet<TypeIdentifier> interestingtrgttypes = new HashSet<TypeIdentifier>();
			foreach(TypeIdentifier tt in this.m_types)
			{
				if(tt.IsCollectionType || tt.IsKeyValType || tt.NameValue.StartsWith("System."))
					continue;

				rectypeset.Clear();
				psf.Clear();
				alreadytried.Clear();
				foreach(OffsetIdentifier irn in tt.AllOffsetIdentifiers)
				{
					interestingtrgttypes.Clear();
					ReadThroughPossibleTargetTypesOfOffset(irn, interestingtrgttypes, new HashSet<TypeIdentifier>());
					bool rwith = FindRecLoopFrom(psf, alreadytried, rectypeset, tt, null, interestingtrgttypes);
				}

				if(rectypeset.Count != 0)
				{
					foreach(TypeIdentifier rctn in rectypeset)
					{
						if(!this.m_recwith.ContainsKey(rctn))
							this.m_recwith.Add(rctn, new HashSet<TypeIdentifier>());
						this.m_recwith[rctn].UnionWith(rectypeset);
					}

					//DEBUG
					//Console.WriteLine("Recursive With:");
					//foreach(TypeIdentifier rctn in rectypeset)
					//	Console.WriteLine(rctn.ToString() + " ");
					//Console.WriteLine();
					//DEBUG
				}
			}
		}

		/// <summary>
		/// Starting from starttype see if we can find any loops in the type graph that proceed along a uniform set of edge types.
		/// </summary>
		private static bool FindRecLoopFrom(Stack<TypeIdentifier> psf, HashSet<TypeIdentifier> alreadytried, HashSet<TypeIdentifier> typesinloop, TypeIdentifier starttype, TypeIdentifier currenttype, HashSet<TypeIdentifier> subsumedbytypes)
		{
			if(starttype == currenttype)
			{
				typesinloop.Add(starttype);
				return true;
			}
			else if(psf.Contains(currenttype) || alreadytried.Contains(currenttype))
			{
				return false;
			}
			else
			{
				if(currenttype == null)
					currenttype = starttype;

				bool cyclefound = false;
				psf.Push(currenttype);
				bool readthroughtype = (currenttype.IsCollectionType || currenttype.IsKeyValType);

				if(readthroughtype || subsumedbytypes.Contains(currenttype))
				{
					foreach(OffsetIdentifier rfn in currenttype.AllOffsetIdentifiers)
					{
						foreach(TypeIdentifier pttn in rfn.OffsetTypes)
						{
							bool found = FindRecLoopFrom(psf, alreadytried, typesinloop, starttype, pttn, subsumedbytypes);
							cyclefound |= found;
						}
					}
				}

				psf.Pop();
				alreadytried.Add(currenttype);
				if(cyclefound)
					typesinloop.Add(currenttype);

				return cyclefound;
			}
		}

		/// <summary>
		/// We aren't really interested in container or keyvalue types so this reads through the to contained types for fields that point to these
		/// and for fields that point to other objects just returns the target type.
		/// </summary>
		private static void ReadThroughPossibleTargetTypesOfOffset(OffsetIdentifier intrn, HashSet<TypeIdentifier> interestingtrgttypes, HashSet<TypeIdentifier> seentypes)
		{
			foreach(TypeIdentifier tt in intrn.OffsetTypes)
			{
				interestingtrgttypes.Add(tt);

				if(!seentypes.Contains(tt))
				{
					seentypes.Add(tt);

					//if the type is a container we want to know about the types in (pointed to by it) as they are what is interesting so keep pushing down
					if(tt.IsCollectionType || tt.IsKeyValType)
					{
						foreach(OffsetIdentifier irn in tt.AllOffsetIdentifiers)
							ReadThroughPossibleTargetTypesOfOffset(irn, interestingtrgttypes, seentypes);
					}
				}
			}
		}

		/// <summary>
		/// Given a set of types compute the set of all types that they may be recursive with and place this info into the given set.
		/// </summary>
		internal void ComputeRecWithSetForSetOfTypes(HashSet<TypeIdentifier> ts1, HashSet<TypeIdentifier> recwithset)
		{
			foreach(TypeIdentifier tt in ts1)
			{
				if(!tt.IsSpecialNullType)
					recwithset.UnionWith(this.m_recwith[tt]);
			}
		}
	}
}
